package 代码随想录_贪心算法;

/**
 * @author zx
 * @create 2022-07-06 21:09
 */
public class 跳跃游戏_55 {
    /**
     * 不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围.
     * 这个范围内,别管是怎么跳的,反正一定可以跳过来.
     * 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点.
     * 每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围.
     * 贪心算法局部最优解：每次取最大跳跃步数(最大覆盖范围),整体最优解：最后得到整体最大覆盖范围,看是否能到终点
     */
    public boolean canJump(int[] nums) {
        int cover = 0;//跳跃覆盖范围
        for(int i = 0;i <= cover;i++){// 注意这里是小于等于cover
            cover = Math.max(i + nums[i],cover);
            if(cover >= nums.length - 1){
                return true;// 说明可以覆盖到终点了
            }
        }
        return false;
    }
}
